Lightweight Asynchronous Conferencing System (LACS) 1.1
______________________________________________
LACS uses a rumor mongering algorithm to spread messages: When it first hears a message, it considers it to be "hot." It then tries to tell other machines that it knows the hot message. So long as the machines it talks to haven't heard the message, the message stays "hot." But the more machines it finds have already heard the message, the colder the message becomes.
The algorithm is based on the paper Epidemic Algorithms for Replicated Database Maintenance, by Demers, Gealy, Greene, Hauser, Irish, Larson, Manning, Shenker, Sturgis, Swinehart, Terry, and Woods, Xerox PARC technical report CSL-89-1.
From a research perspective (of course we never do these things for fun, there's always a "reason"), there are two main points to the program: First, the distribution algorithm is totally distributed. There is no central server, no central coordination, and no central control. Drop two LACS in a network and they'll find each other and start gossiping. With more than two, it becomes almost impossible to eradicate either them or the messages they spread (you have to kill the message on each and every machine that's heard it). Second, it's a form of communication halfway between synchronous, real-time, short-term conferencing, and asynchronous, long-term, bulletin boards. I don't know of any other system that fills quite the same communications niche.
Using the Program:
LACS is intended to be left running in the background under MultiFinder. It will gossip away, using very little CPU, and not much more memory (400K). When it finds a new message, it will let you know with the Notification Manager (but you can turn that off if you like).
LACS has three windows: Messages, New Message, and Status. Each of the windows can be closed. Each window can be reopened and brought to the front by an entry in the Windows menu.
Messages Window. This window displays messages as they come in. New messages appear in the "Unread Messages" section. The first few words of each message is displayed. Clicking on a message in this area displays the full text of the message in the lower half of the window, and moves the message to the "Read Messages" section. Besides the text of the message, the origination and expiration dates are also displayed. Messages are automatically deleted when the expiration date arrives. Messages which are still hot have a diamond preceding them in the read/unread message lists. Messages cool off after about four or five days.
New Message Window. This window is where new messages are entered. To start a message, just type it in, select an expiration date (the default is to expire the message in four days), and click Send Message or hit Enter. (Note that you can't include a return within the body of a message.) If you change the expiration date, it will stay that many days in the future — i.e., it increments by one day every day.
Status Window. This window shows various pieces of information about the system. It lists the other machines the program is directly spreading messages to, how many messages it's seen, how many it's successfully passed on, and how many of the current ones are hot and how many are cold.
The Messages menu provides two commands: Mark All Messages Read moves all of the unread messages to the "Read Messages" category, just as if you'd gone through and clicked every one. Delete All Messages removes all messages from both categories. Note, however, that this also deletes the program's memory of what messages it's seen, so you'll probably get many of the same messages back again from other machines. Delete All Messages is not intended to be used in "normal" operation.
When you quit the program, it saves the messages, together with the positions of all the windows, to a file in your system folder in a file named "LACS Settings". When you restart the program later, it will be right back where you were when you quit.
___________________________
LACS users don't need to read past this point. If you want to write a program to inject or capture messages, or if you're just curious, read on.
___________________________
For You Technical Types:
Build note: LACS should be built by executing "MABuild -needsSystem6 -nodebug". Since it uses the notification manager, it requires System 6.0 or later.
When LACS gets a new message, it marks it as "hot." It then periodically tries to tell another machine about it. The other machine answers either "yeah, that's hot," or "nah, I've already heard it." If the answer is "already heard it," then LACS increments a counter associated with the message. That counter helps determine when the message becomes "cold."
In order to find other machines to gossip with, LACS periodically looks at the network and builds a list of local AppleTalk zones. Then it periodically picks a zone, looks for other LACS in that zone, and adds one of those machines to it's list of gossipers. It has a maximum of ten gossipers in the list, after which it replaces an existing one.
The algorithm stated above has a lot of parameters which are not hard-wired into the program. Instead, these can be set and changed. In fact, it is possible to spread a message which changes them. (Note that this is dangerous, since you can easily change them such that the LACSs can't talk to each other any more. For this reason, it's not possible to create such a message with the normal LACS application.) The rest of this sections describes the details of the algorithm, including those parameters which are changeable and those which are not.
The zone list is updated once every four hours. The list of other gossipers is updated every eight seconds until one is found in another zone; then it's updated every twenty minutes. This tends to get people connected quickly, even on large networks like Apple's. When updating the list, the local AppleTalk zone is looked at 1/nth of the time (default: 1/2); otherwise, another zone is picked at random (this tends to lower the impact on the network by encouraging localized connections).
LACS tries to spread rumors every x seconds (default: 30 seconds). When LACS goes to spread a message, it may push a message to the other side (default: yes), and/or it may pull (ask for) a message (default: no). But if it has less than n message (default: 5), then instead of spreading messages, it always pulls (asks for) messages from other gossipers; in this case, it asks for hot messages if they're available, but it will take cold messages if there are no hot messages. (Note: This special case is done so that new users get something fairly quickly when they start running LACS.)
LACS keeps a counter associated with each message which tells how many times it tried to pass the message on and was told it was a cold message. This counter determines both when a message becomes cold, and also how long to wait to try and spread this message again. The message becomes cold either deterministically or probabilistically (default: deterministically). If deterministically, it becomes cold when the counter reaches n; if probabilistically, it becomes cold with 1/n probability each time it increments the counter (default: n = 30). If the message is still hot, it is not passed on again until (b*c)^x seconds have passed, where c is the cold passes counter, and b and x are parameters (default: b = 5, x = 2).
The program does not keep any information with each message as to where it's been passed on to. Therefore, it is quite possible, even likely, that it will try to spread the message to the same gossiper more than once.
For You REALLY Technical Types:
Choices in the LACS communications design were explicitly made to simplify connectivity between LACS and other systems. It is fairly simple, therefore, to write a program in another language to inject new messages, or to captures the messages which are in the system.
The program registers itself under NBP as the chooser name, type "LACS". Communication is done using ADSP, and using ASCII text only (i.e., no binary data). The communication stream is broken into messages, which are terminated by a carriage return and also by an end-of-message flag. LACS itself requires the EOM flag to be set, and ignores the carriage return. Within the messages are fields, each of which is terminated with a tab (even the last one, before the return). The first field is a command string; the rest of the fields are parameters to that command.
Current commands are listed below. Parameters are listed as in a Pascal function call, following the command name. Parameter types indicate what the parameter is translated into when received, not how it's stored in the message; all parameters are ASCII text in the message.
"Rumor"(filter: Str32; type: Str32; text: StringHandle; startDate: longInt; expirationDate: longInt) - send a message. Dates are in seconds since 1904 (as returned by GetDateTime). If the expirationDate is 0, that indicates no expiration date.
"HotRumor"(filter: Str32; type: Str32; text: StringHandle) - sent in reply to "Rumor", this command indicates that the given message has not been seen before by the sender (note that message equality is based on filter/type/text but not on start or expiration date).
"ColdRumor"(filter: Str32; type: Str32; text: StringHandle) - sent in reply to "Rumor", this command indicates that the given message has been seen before by the sender.
"Pull" - requests that the receiver send a new hot message using the "Rumor" message.
"PullCold" - requests that the receiver send a new message. If a hot message is available, send that. If not, then send a cold message.
"Params" - requests that the receiver send the current algorithm parameters of the receiving machine. Parameters are sent in the same format as in a "Params" type message (see below).
The filter and type are part of each message but are not currently displayed to the user. These are provided for future expansion. Each is limited to 32 characters. The filter field is intended to provide a way to have "private" message sessions. LACS will currently only display messages with a filter of "Rumor", and will always generate messages with that filter. The type field is intended to provide a way to categorize messages. LACS will currently only generate messages of type "General", but will display messages of any type.
If LACS receives a message of type "Params", it will interpret the text as new parameter settings to it's message distribution algorithm (see the previous section). In this case, the text consists of parameter name/parameter value pairs, with single spaces in between. Parameters are (n indicates numeric; b indicates "true" or "false"):
"InZoneSearch" n — Search for gossipers in the local zone 1/nth of the time.
"Push" b — Push messages when spreading.
"Pull" b — Pull messages when spreading.
"PullOnLess" n — Pull hot or cold messages if there are less than n messages.
"Count" b — Use deterministic count to cool messages (as opposed to probabilistic).
"CountValue" n — If deterministic cooling, considers messages cold after n bad tries to spread them. If probabilistic spreading, cool messages 1/nth of the time after each bad try.
"Feedback" b — If false, always consider a message pass to have failed, even if it hasn't. (This is useful for simulating the distribution algorithm in the case where it does not return succeeded/failed information.)
"DelayBase" n — parameter to message spreading delay formula: b in (c*b)^x.
"DelayExp" n — parameter to message spreading delay formula: x in (c*b)^x.
